#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include "huf_compress.cpp"
using namespace std;

//索引文档：链表储存
class Doc
{
public:
    int Doc_num;//文档编号
    int Doc_text_pos;//对应的文本的位置
    Doc *next;//指向下一个文件
    Doc()
    {
        Doc_num=0;
        Doc_text_pos=-1;
        next = NULL;
    }
};

//词条
class Entry
{
public:
    vector<int>num_word;
    string key_word;//关键字
    Doc *head;//头指针
    int sumDoc;//出现在哪些文档内，记录词频，进行编码
    Entry(string word){
        key_word=word;
        head=NULL;
        sumDoc=0;
    }
    //与运算
    Entry* AND(Entry *e1){
        Entry *tmp = new Entry("("+key_word +"&" + e1->key_word+")");

        Doc *p1=head->next,*p2=e1->head->next,*p3 = tmp->head = new Doc();

        while(p1!=NULL && p2!=NULL)
        {
            if(p1->Doc_num < p2->Doc_num)
                p1=p1->next;
            else if(p1->Doc_num > p2->Doc_num)
                p2=p2->next;
            else
            {
                tmp->sumDoc+=2;
                Doc *q1 = new Doc();
                Doc *q2 = new Doc();
                q1 = p1;
                q2 = p2;
                q1->next=q2->next=NULL;
                p3->next = q1;
                q1->next=q2;
                p3=q2;
                p1=p1->next;
                p2=p2->next;
            }
        }
        return tmp;
    }
    //或运算
    Entry* OR(Entry *e1){
        Entry *tmp = new Entry("复合单词");
        Doc *p1=e1->head->next,*p2=head->next,*p3 = tmp->head = new Doc();
        while(p1!=NULL && p2!=NULL)
        {
            Doc *q = new Doc();
            if(p1->Doc_num < p2->Doc_num)
            {
                q->Doc_num=p1->Doc_num;
                q->Doc_text_pos=p1->Doc_text_pos;
                p1=p1->next;
            }
            else if(p1->Doc_num > p2->Doc_num)
            {
                q->Doc_num=p2->Doc_num;
                q->Doc_text_pos=p2->Doc_text_pos;
                p2=p2->next;
            }
            else if(p1->Doc_num == p2->Doc_num)
            {
                q = p1;
                Doc *q2 = new Doc();
                q2 = p2;
                p3->next = q2;
                p3 = p3->next;
                tmp->sumDoc++;

                p1=p1->next;
                p2=p2->next;
            }
            p3->next = q;
            p3 = p3->next;
            tmp->sumDoc++;
        }
        while(p1!=NULL){
            Doc *q = new Doc();
            q->Doc_num=p1->Doc_num;
            q->Doc_text_pos=p1->Doc_text_pos;
            p1=p1->next;
            tmp->sumDoc++;
        }
        while(p2!=NULL){
            Doc *q = new Doc();
            q->Doc_num=p2->Doc_num;
            q->Doc_text_pos=p2->Doc_text_pos;
            p2=p2->next;
            tmp->sumDoc++;
        }
        return tmp;
    }

};

string text[11];//原文章文本
vector<vector<string>>dictionary;//词典
map<string,int>Map;//关键字和频数
vector<Entry*>Dic;//词典：词条的集合体

//fruits-after目录下的文本文件
const char *a_name[10]=
{
    "fruits-after\\apple.txt",
    "fruits-after\\cherry.txt",
    "fruits-after\\grape.txt",
    "fruits-after\\mangosteen.txt",
    "fruits-after\\orange.txt",
    "fruits-after\\peach.txt",
    "fruits-after\\pear.txt",
    "fruits-after\\pineapple.txt",
    "fruits-after\\pomelo.txt",
    "fruits-after\\watermelon.txt"
};
//fruits-before目录下的文本文件
const char *b_name[10]=
{
    "fruits-before\\apple.txt",
    "fruits-before\\cherry.txt",
    "fruits-before\\grape.txt",
    "fruits-before\\mangosteen.txt",
    "fruits-before\\orange.txt",
    "fruits-before\\peach.txt",
    "fruits-before\\pear.txt",
    "fruits-before\\pineapple.txt",
    "fruits-before\\pomelo.txt",
    "fruits-before\\watermelon.txt"
};

//把原文本用string text[11]储存起来
void Creat_string_text(){
    for(int i=0;i<10;i++)
    {
        string tmp="";
        char str[128];
        FILE *fin=fopen(b_name[i],"r");
        while(fgets(str,128,fin)!=NULL)
            tmp+=str;
        text[i+1]=tmp;
    }
}

/**创建词典**/
void Creat_Vector()
{
    for(int i=0;i<10;i++)
    {
        FILE *fin = fopen(a_name[i],"r");
        vector<string>v;
        char ch;
        string str;
        ch = getc(fin);
        while(ch !=EOF){
            if(isalpha(ch)||isdigit(ch))str+=ch;
            else if(str.length()<=2);
            else {
                v.push_back(str);
                str = "";}
            ch = getc(fin);
        }
        dictionary.push_back(v);
    }
}

//**建立倒排索引
void Inverted_Index(){
    //1. 把所有的词都放入Vector类型的dictionary中
    Creat_Vector();
    //2. 为了使得词条不重复，使用Map容器。
    for(int i=0;i<10;i++){
        for(int j=0;j<dictionary[i].size();j++)
        {
            Map[dictionary[i][j]]++;
        }
    }

    //3. *建立倒排索引
    for(auto it : Map)
    {
        //为每个词条建立索引表
        string str = it.first;
        Entry *entry = new Entry(str);
        Doc *p=entry->head = new Doc();
        int sumDoc=0;
        /*规则：如果能找到，就建立索引链表，并且将原文的片段记录进去（前后4个）*/
        for(int i=1;i<=10;i++){
            int pos = text[i].find(str);
            int len = str.length();
            if(pos!= string::npos){
                sumDoc++;
                Doc *q = new Doc();
                q->Doc_text_pos=pos;
                q->Doc_num=i;
                p->next=q;
                p=p->next;
            }
            //记录文档编号
            entry->num_word.push_back(i);
        }
        entry->sumDoc=sumDoc;
        Dic.push_back(entry);
    }
}

//找到相应的词条对象，方便做布尔运算
Entry* Find_Entry(string str)
{
    /****测试成功*****/
    //一条一条找
    Entry *tmp = new Entry(str);
    for(int i=0;i<Dic.size();i++)
    {
        tmp = Dic[i];
        if(tmp->key_word == str)
        {
            cout << "字符串在词典中被成功找到！" << endl;
            return tmp;
        }
    }
    cout << "字符串没有被成功找到..." << endl;
    return NULL;
}

//查询单词附近信息
string Show_Text(int Doc_num,int Doc_text_pos,int Word_len)
{
    if(Doc_num<0 || Doc_text_pos <0){
        return "查询不到文本。";
    }
    string tmp="";
    int pre_count=0,p_pos=Doc_text_pos;
    while(p_pos>0&&pre_count<4){
        p_pos--;
        pre_count++;
    }
    int pro_count=0,text_len=text[Doc_num].length();
    p_pos=Doc_text_pos;
    while(p_pos<text_len&&pro_count<4){
        p_pos++;
        pro_count++;
    }
    return "..." + text[Doc_num].substr(Doc_text_pos-pre_count,pre_count+Word_len+pro_count) + "...";
}

//查询字符串
void Show_Entry(Entry *&entry)
{
    cout << "词条打印输出如下"  << endl;
    Doc *p=entry->head->next;
    cout << "一共有" << entry->sumDoc << "个文档：" << endl;
    cout << entry->key_word << ": " << endl;
    while(p!=NULL)
    {
        cout << "Doc" << p->Doc_num << " : " << Show_Text(p->Doc_num,p->Doc_text_pos,(entry->key_word).length()) << endl;
        p=p->next;
    }
}

//**** 测试 ****//
void Bool_find(string str1,string str2,char ch)
{
    Entry *e1 = Find_Entry(str1);
    Entry *e2 = Find_Entry(str2);
    if(e1 && e2)
    {
        Entry *tmp = NULL;
        if(ch=='|'){
            tmp = e1->OR(e2);
        }
        else{
            tmp = e1->OR(e2);
        }
        if(tmp->sumDoc==0){
            cout << "该复合词组不存在于字典中...." << endl;
        }
        else Show_Entry(tmp);
    }
    else{
        if(!e1)cout << "第一个词条不存在于词典中...." << endl;
        if(!e2)cout << "第二个词条不存在于词典中...." << endl;
    }
}

void Show_help()
{
    cout << "+---------------------------------------+" << endl;
    cout << "|【-help：】                        \t|" << endl;
    cout << "|【查询单个词条，请输入：1】        \t|"  << endl;
    cout << "|【查询复合词组，请输入：2】        \t|"  << endl;
    cout << "|【查询网址间路径，请输入：3】      \t|"  << endl;
    cout << "|【压缩或者解压文本文件，请输入：4】\t|" << endl;
    cout << "|【清除控制台查询信息，请输入：5】  \t|" << endl;
    cout << "|【退出查询功能，请输入：6】        \t|" << endl;
    cout << "+---------------------------------------+" << endl;
}
void function1()
{
    cout << "【请输入您想查询的词条：】" << endl;
    string str;
    cin >> str;
    cout << "等待查询结果... ..." << endl;
    Entry *tmp = Find_Entry(str);
    if(tmp==NULL){
        cout << "【抱歉，未查询到该词条。】" << endl;
    }
    else{
        Show_Entry(tmp);
    }
}
void function2()
{
    cout << "【查询复合词组格式如下：】" << endl;
    /*cout << "【词条 & 词条 或者 词条 | 词条】" << endl;
    string str1,str2;
    char ch;
    while(true)
    {
        cout << "请输入：" << endl;
        cin >> str1 >> ch >> str2;
        if(ch!='&' && ch!='|'){
            cout << "【输入格式错误！请重新输入！】" << endl;
            continue;
        }
        Bool_find(str1,str2,ch);
        break;
    }
    */
    //输入单词输出他所在的文档
    /****逆波兰式******/
    char str;//一次输入一个字符
    queue<string> st_word;//存放总栈
    stack<string> st_op;//存放运算符栈
    string tmp_word="";//存放word
    getchar();
    while(true)
    {
        scanf("%c",&str);
        if(str=='(')
        {
            if(tmp_word!="")
            {
                st_word.push(tmp_word);
                tmp_word="";
            }
            tmp_word+=str;
            st_op.push(tmp_word);
            tmp_word="";
        }
        else if(str==')')
        {
            if(tmp_word!="")
            {
                st_word.push(tmp_word);
                tmp_word="";
            }
            while(true)
            {
                string tmp_op=st_op.top();
                st_op.pop();
                if(tmp_op=="(")
                    break;
                st_word.push(tmp_op);
            }
        }
        else if(str=='|'||str=='&')
        {
            if(tmp_word!="")
            {
                st_word.push(tmp_word);
                tmp_word="";
            }
            tmp_word+=str;
            if(!st_op.empty())
            {
                while(true)
                {
                    string tmp_op=st_op.top();
                    if(tmp_op=="(")
                        break;
                    st_op.pop();
                    st_word.push(tmp_op);
                    if(st_op.empty())
                        break;
                }
            }
            st_op.push(tmp_word);
            tmp_word="";
        }
        else if(str==' ')
        {
            if(tmp_word!="")
            {
                st_word.push(tmp_word);
                tmp_word="";
            }
        }
        else if(str=='\n')
        {
            if(tmp_word!="")
            {
                st_word.push(tmp_word);
                tmp_word="";
            }
            while(!st_op.empty())
            {
                string tmp_op=st_op.top();
                st_op.pop();
                st_word.push(tmp_op);
            }
            break;
        }
        else
        {
            tmp_word+=str;
        }
    }
    //计算
    stack<string> st_word2;//存放单词
    stack<Entry*> st_last;
    while (!st_word.empty())
    {
        //cout << st_word.size()<< endl;
        string tmp = st_word.front();
        st_word.pop();
        if (tmp == "|")
        {
            //cout << "| 的单词个数 ： " << st_last.size() << endl;
            Entry* a1 = st_last.top();
            st_last.pop();
            Entry* a2 = st_last.top();
            st_last.pop();
            Entry* a3 = a1->OR(a2);
            st_last.push(a3);
        }
        else if (tmp == "&")
        {
            //cout << "& 的单词个数 ： " << st_last.size() << endl;
            Entry* a1 = st_last.top();
            st_last.pop();
            Entry* a2 = st_last.top();
            st_last.pop();
            Entry* a3 = a1->AND(a2);
            st_last.push(a3);

        }
        else
        {
            Entry* arr_z = Find_Entry(tmp);
            st_last.push(arr_z);
            st_word2.push(tmp);
        }
    }
    Entry* anser = st_last.top();
    st_last.pop();
    Show_Entry(anser);
}
void function3()
{
    /*
    double pro[11][11] = {
        {},
        {0,1.0000,0.8530,0.8636, 0.1771, 0.2546, 0.1262, 0.2162, 0.0488, 0.2061,0.1165},
        {0,0.8530, 1.0000, 0.2819, 0.4287, 0.3330, 0.3598, 0.8237, 0.7063, 0.9565,0.4772},
        {0,0.8636, 0.2819, 1.0000, 0.0429, 0.8887, 0.0297, 0.5160, 0.7141, 0.7820,0.9492},
        {0,0.1771, 0.4287, 0.0429, 1.0000, 0.4003, 0.0611, 0.7951, 0.2877, 0.2106,0.5884},
        {0,0.2546, 0.3330, 0.8887, 0.4003, 1.0000, 0.9987, 0.0640, 0.5897, 0.8763,0.6273},
        {0,0.1262, 0.3598, 0.0297, 0.0611, 0.9987, 1.0000, 0.9034, 0.9996, 0.2579,0.2076},
        {0,0.2162, 0.8237, 0.5160, 0.7951, 0.0640, 0.9034, 1.0000, 0.3385, 0.2499,0.6091},
        {0,0.0488, 0.7063, 0.7141, 0.2877, 0.5897, 0.9996, 0.3385, 1.0000, 0.4253,0.8842},
        {0,0.2061, 0.9565, 0.7820, 0.2106, 0.8763, 0.2579, 0.2499, 0.4253, 1.0000,0.0953},
        {0,0.1165, 0.4772, 0.9492, 0.5884, 0.6273, 0.2076, 0.6091, 0.8842, 0.0953,1.0000},
    };
    */
    double pro[11][11];
    for (int i = 1; i <= 10; i++)
        for (int j = 1; j <= 10; j++)
            cin >> pro[i][j];
    for(int i=1;i<=10;i++)
        for(int j=1;j<=10;j++)
            for(int k=1;k<=10;k++)
            {
                if(i==j||j==k||k==i)continue;
                if(pro[i][k]*pro[k][j]>pro[i][j])
                    pro[i][j]=pro[i][k]*pro[k][j];
            }
    cout << "Tip: 文档1（行） ---> 文档2（列） 的最短距离：" << endl << endl;;
    cout << "   1      2      3      4      5      6      7      8      9      10      " << endl;
    for(int i=1;i<=10;i++)
    {
        printf("%-3d",i);
        for(int j=1;j<=10;j++)
        {
            printf("%.4f ",1/pro[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}


int main()
{
    Creat_string_text();
    //建立倒排索引
    Inverted_Index();
    char op;
    while(true){
        Show_help();
        cout << "请输入：";
        cin >> op;
        if(!(op>='1' && op<='6')){
            cout << "【输入格式错误！请您重新输入！】" << endl;
            continue;
        }
        switch (op-'0'){
        case 1:
            function1();
            break;
        case 2:
            function2();
            break;
        case 3:
            function3();
            break;
        case 4:
            huf_Compress();
            break;
        case 5:
            system("cls");
            break;
        }
        if(op == '6'){
            cout << "【本次查询结束。】" << endl;
            break;
        }
    }
    return 0;
}
